package com.study.dataStructure.sortAlgorithms;

import com.study.dataStructure.util.ArraysUtil;

import java.util.Arrays;

/**
 * @author tiny
 * @date 2021/11/1 20:44
 * @Description: 基数排序
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] nums = ArraysUtil.createRandomArr(200,1000);
        System.out.println(Arrays.toString(nums));
        System.out.println( ArraysUtil.isSort(nums) );
        radixSort(nums);

        System.out.println(Arrays.toString(nums));
        System.out.println( ArraysUtil.isSort(nums) );
    }

    private static void radixSort(int[] nums) {
        //获取最大数的位数（要遍历的总次数）
        int count = getMaxCount(nums);

        for (int i = 0; i < count; i++) {
            int[][] bucket = new int[10][0]; //二维数组
            //第一轮按个位数分到不同的桶
            for (int j = 0; j < nums.length; j++) {
                int flagNum = ( nums[j] / ((int)Math.pow(10,i)) ) % 10;
//                System.out.println(nums[j]+"--------------------"+flagNum);
                //扩容数组
                bucket[flagNum] = reseize(bucket[flagNum],nums[j]);
            }
            //一轮下来元素都放入桶中对应位置； 再合并
            mergeBucket(bucket,nums);
        }
    }

    private static void mergeBucket(int[][] bucket,int[] nums) {
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int j =0; j< bucket[i].length; j++) {
                nums[index++] = bucket[i][j];
            }
        }
    }

    private static int[] reseize(int[] link, int num) {
        int reSize = link.length + 1;
        int[] newArr = new int[reSize];
        for (int i = 0; i < link.length; i++) {
            newArr[i] = link[i];
        }
        newArr[reSize-1] = num;
        return newArr;
    }

    private static int getMaxCount(int[] nums) {
        int maxLength = 0 ;
        for (int num : nums) {
            int length = String.valueOf(num).length();
            if(length > maxLength){
                maxLength = length;
            }
        }
        return maxLength;
    }
}
